package com.example.myapplication.Algorithm.SumTwoNumbers;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class SumTwoNumbers {
    //求两数之和为10的下标
        public static void main(String[] args){
            System.out.println(Arrays.toString(solution(new int[]{1,2,3,4,5,6},10)));
            System.out.println(Arrays.toString(solution1(new int[]{1,2,3,4,5,6},10)));
            System.out.println(Arrays.toString(twoSearch(new int[]{1,2,3,4,5,6},10)));
            System.out.println(Arrays.toString(twoPoint(new int[]{1,2,3,4,5,6},10)));//O(N)
        }

        ///暴力算法
        public static int[] solution(int[] nums, int target){
            for(int i=0;i<nums.length;i++){
                for(int j= i+1;j<nums.length;j++){
                    if(nums[i] + nums[j] == target){
                        return new int[]{i,j};
                    }
                }
            }
            return new int[0];
        }

        ///优化暴力算法
        public static int[] solution1(int[] nums, int target){
            Map<Integer,Integer> map  = new HashMap<Integer,Integer>();

            for(int i=0;i<nums.length;i++){
                if(map.containsKey(target - nums[i])){
                    return new int[]{map.get(target-nums[i]),i};
                }
                map.put(nums[i],i);
            }
            return new int[0];
        }

        ///二分法
        public static int[] twoSearch(int[] numbers,int target){
            for (int i=0;i<numbers.length;i++){
                int low = i;
                int hight = numbers.length-1;
                while (low<=hight){
                    int mid = (hight-low)/2+low;
                    if(numbers[mid] == target - numbers[i]){
                        return new int[]{i,mid};
                    }else if(numbers[mid] > target - numbers[i]){
                        hight = mid-1;
                    }else{
                        low = mid+1;
                    }
                }

            }
            return new int[]{0};
        }
        ///算指针算法
        public static int[] twoPoint(int[] numbers,int target){
            int low = 0;
            int hight = numbers.length-1;
            while (low<=hight){
                int sum = numbers[low] + numbers[hight];
                if(sum == target){
                    return new int[]{low,hight};
                }else if(sum<target){
                    low++;
                }else{
                    hight++;
                }
            }
            return new int[]{0};
        }
    }